package com.kotlin

/**
 * @author 张一鸣
 * @since 2018.4.18
 * 算法第四版，第二章
 * 排序
*/
import java.util.Random
import kotlin.system.measureTimeMillis


class Sorting{

    /*
    一个细节，kotlin对于泛型的管理支持Java传统的T和E类型，
    但是需要用关键字in、out、where等确定是输入还是输入使用泛型

    kotlin则支持*和Any两种关键字，
    Any当真就是为所欲为
    *则等同于out Any?，可以随意读取任意类型，却不能随意将原本变量改动为任意泛型

    但是这里，输入拥有特定接口类型的泛型的时候，需要添加一个标签，进行指定
    */
    fun <T : Comparable<T>> selectSort(a: Array<T>): Array<T> {

        for (i in 0.until(a.size)) {
            var min = i  // 默认目前位置的数字最小
            for (j in (i+1).until(a.size)) {  // 内层嵌套一个循环，目的就是找出后边所有值中最小值的位置
                if (a[j].compareTo(a[min]) < 0 ) min = j
            }
            a[min] = a[i].also { a[i] = a[min] }  // 将最小值提到前边来
        }

        return a
    }


    /*
    插入排序，确实速度快一些，
    外层从左至右依次遍历，内层，则将从右至左的所有数值排序
    */
    fun <T: Comparable<T>> insertSort(a: Array<T>): Array<T> {
        for (i in 0.until(a.size)) {
            for (j in (a.size-1).downTo(i+1)) {
                if (a[j].compareTo(a[j-1]) < 0) {
                    a[j] = a[j-1].also { a[j-1] = a[j] }
                }
            }
        }

        return a
    }

    /*
    希尔排序
    其实没怎么看懂，就是貌似很牛逼，个人感觉特别想merge sort

    主要思路就是通过将原本的数据划分为不超过原长1/3的小段，将每个小段分别初步排序，
    然后每一小段划分为更小的一段，继续排序，
    最终统一为一个整体
    */
    fun <T: Comparable<T>> shellSort(a: Array<T>): Array<T> {
        val N = a.size
        var h = 1

        while (h < N/3) h = 3*h + 1
        while (h >= 1) {
            for (i in h.until(N)) {
                for (j in i downTo h step h) {
                    if (a[j].compareTo(a[j-h]) < 0) {
                        a[j] = a[j-h].also { a[j-h] = a[j] }
                    }

                }
            }
            h /= 3
        }

        return a
    }

    /*
    归并排序
    套了几层皮，借用了Java传递参数以传递指针为主的特性，
    免去了多个返回的麻烦，直接对原数组进行操作完成排序工作
     */
    fun <T: Comparable<T>> mergeSortTop2Bottom(a: Array<T>): Array<T> {
        this.mainMergeSort(a, 0, a.size-1)
        return a
    }

    private fun <T: Comparable<T>> mainMergeSort(a: Array<T>, low: Int, high: Int) {
        if ((low - high) == 0) return

        val mid = (low + high)/2

        mainMergeSort(a, low, mid)
        mainMergeSort(a, mid + 1, high)
        merge(a, low, high, mid)
    }

    private fun <T: Comparable<T>> merge(a: Array<T>, low: Int, high: Int, mid: Int) {
        val leftArray = a.copyOfRange(low, mid + 1)
        val rightArray = a.copyOfRange(mid+1, high + 1)
        var i = 0
        var j = 0

        /*
        归并排序其他地方都好理解，唯独此处，
        这里的意思就是将整个数组拆分成左右两部分
        然后左边没有遍历完成的情况下，优先选用左边的数据，其中硬性条件为左边的这个值，要小，否则就右边进一位
        另外，就是右边已经全部遍历完成了，这样把剩下左边的持续读取完成
        */
        for (k in low..high) {
            if (i < leftArray.size && ((j >= rightArray.size) || (leftArray[i] <= rightArray[j]))) {
                a[k] = leftArray[i]
                i++
            } else {
                a[k] = rightArray[j]
                j++
            }
        }

    }

    /*
    自下而上的并归排序
    将原数组按照1*1,2*2，4*4 ...的形式分割成小段记性排序
    这种形式的排序，链表性能较好，写法更加简单
     */
    fun <T: Comparable<T>> mergeSortBottom2Top(a: Array<T>): Array<T> {
        var i = 1
        while (i < a.size) {
            var j = 0
            while (j < a.size - i) {
                j += 2*i
                merge(a, j, Math.min(j-1, a.size-1), j+i-1)
            }
            i += i
        }
        return a
    }
}


// 就是print信息
private fun <T : Comparable<T>> show(a: Array<T>) {
    for (i in a) print("$i ")
    println()
}

// 通过ClosedRange生成随机数
fun ClosedRange<Int>.random() =
        Random().nextInt(endInclusive - start) +  start


fun main(args: Array<String>) {
    val sorter = Sorting()

    val sample = ArrayList<Int>()
    for (i in 0..1000) {
        sample.add((0..1000).random())
    }

    // 运行选择排序
    var time = measureTimeMillis {
        show(sorter.selectSort(sample.toTypedArray().clone()))
    }
    println("Select Sort spend: $time")

    // 运行插入排序
    time = measureTimeMillis {
        show(sorter.insertSort(sample.toTypedArray().clone()))
    }
    println("Insert Sort spend: $time")


    // 运行希尔排序
    time = measureTimeMillis {
        show(sorter.shellSort(sample.toTypedArray().clone()))
    }
    println("Shell Sort spend: $time")

    // 运行归并排序
    time = measureTimeMillis {
        show(sorter.mergeSortTop2Bottom(sample.toTypedArray().clone()))
    }
    println("Merge Sort UB spend: $time")

    // 运行归并排序
    time = measureTimeMillis {
        show(sorter.mergeSortBottom2Top(sample.toTypedArray().clone()))
    }
    println("Merge Sort BU spend: $time")

}